#include <cstdlib>
#include "sort.h"

void selection_sort_array(int nums[], int size)
{
    // select the smallest remaining element and put into tmp array end
    int * tmp = (int *)std::malloc(size*sizeof(int));
    bool * marked = (bool *)std::calloc(size, sizeof(bool));
    if(NULL == tmp || NULL == marked)
    {
        return;
    }

    int tmp_end = 0;
    int tiny_index = 0;
    int i = 0;
    bool first_remaining = true;
    while(tmp_end != size)
    {
        first_remaining = true;
        for(i = 0; i < size; ++ i)
        {
            if(marked[i])
            {
                continue;
            }
            if(first_remaining)
            {
                tiny_index = i;
                first_remaining = false;
            }
            else if(nums[i] < nums[tiny_index])
            {
                tiny_index = i;
            }
        }
        marked[tiny_index] = true;
        tmp[tmp_end ++] = nums[tiny_index];
    }
    for(i = 0; i < size; ++ i)
    {
        nums[i] = tmp[i];
    }
    std::free(tmp);
    std::free(marked);
}

